package com.tucc.hello.leetcode.no801_1200.no872;

import com.tucc.hello.tree.Main;
import com.tucc.hello.tree.TreeNode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode root1 = Main.makeTree(Arrays.asList(new Integer[]{1, 2}));
        TreeNode root2 = Main.makeTree(Arrays.asList(new Integer[]{2, 1}));
        System.out.println(solution.leafSimilar(root1, root2));
    }

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        LinkedList<TreeNode> list = new LinkedList<>();
        getLeaf(root1, list);
        return checkLeaf(root2, list) && list.isEmpty();
    }

    public void getLeaf(TreeNode root, List<TreeNode> leafList){
        if(root != null){
            if(root.left == null && root.right == null){
                leafList.add(root);
                return;
            }
            if(root.left != null){
                getLeaf(root.left, leafList);
            }
            if(root.right != null){
                getLeaf(root.right, leafList);
            }
        }
    }

    public boolean checkLeaf(TreeNode root, List<TreeNode> leafList){
        if(root != null){
            if(root.left == null && root.right == null){
                if(leafList.size() == 0){
                    return false;
                }
                TreeNode leaf = leafList.remove(0);
                if(leaf.val != root.val){
                    return false;
                }
            }
            return (root.left == null
                    || checkLeaf(root.left, leafList))
                    && (root.right == null ||
                        checkLeaf(root.right, leafList));
        }
        return true;
    }

}
